/*-------------------------------------------------------------------------
 *
 * parse_cte.c
 *	  handle CTEs (common table expressions) in parser
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/parser/parse_cte.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "catalog/pg_collation.h"
#include "catalog/pg_type.h"
#include "nodes/nodeFuncs.h"
#include "parser/analyze.h"
#include "parser/parse_coerce.h"
#include "parser/parse_collate.h"
#include "parser/parse_cte.h"
#include "parser/parse_expr.h"
#include "utils/builtins.h"
#include "utils/lsyscache.h"
#include "utils/typcache.h"


/* 不允许自引用的上下文的枚举 */
typedef enum
{
	RECURSION_OK,
	RECURSION_NONRECURSIVETERM, /* 在左侧术语内部 */
	RECURSION_SUBLINK,			
/* 在子链接内部 */
	RECURSION_OUTERJOIN,		/* 在外连接的可空侧内部 */
	RECURSION_INTERSECT,		/* 在 INTERSECT (ALL) 之下 */
	RECURSION_EXCEPT			/* 在 EXCEPT (ALL) 之下 */
} RecursionContext;

/* 相关错误消息 --- 每个必须有一个 %s 用于 CTE 名称 */
static const char *const recursion_errormsgs[] = {
	/* RECURSION_OK */
	NULL,
	/* RECURSION_NONRECURSIVETERM */
	gettext_noop("recursive reference to query \"%s\" must not appear within its non-recursive term"),
	/* RECURSION_SUBLINK */
	gettext_noop("recursive reference to query \"%s\" must not appear within a subquery"),
	/* RECURSION_OUTERJOIN */
	gettext_noop("recursive reference to query \"%s\" must not appear within an outer join"),
	/* RECURSION_INTERSECT */
	gettext_noop("recursive reference to query \"%s\" must not appear within INTERSECT"),
	/* RECURSION_EXCEPT */
	gettext_noop("recursive reference to query \"%s\" must not appear within EXCEPT")
};

/*
 * 对于 WITH RECURSIVE，我们必须找到一个没有前向引用的子句成员排序，并确定哪些成员是递归的
 * （即，自我引用）。使用 CteItems 数组而不是 CommonTableExprs 列表来做到这一点是方便的。
 */
typedef struct CteItem
{
	CommonTableExpr *cte;		/* 一个 CTE 用于检查 */
	int			id;				/* 其依赖项的 ID 编号 */
	Bitmapset  *depends_on;		/* 依赖的 CTEs（不包括自身） */
} CteItem;

/* CteState 是我们在树遍历中需要传递的内容 */
typedef struct CteState
{
	/* 全局状态： */
	ParseState *pstate;			/* 全局解析状态 */
	CteItem    *items;			/* CTEs 及额外数据的数组 */
	int			numitems;		/* CTEs 的数量 */
	/* 在树遍历期间的工作状态： */
	int			curitem;		/* 当前正在检查的项目索引 */
	List	   *innerwiths;		/* CommonTableExpr 的列表列表 */
	/* 仅用于 checkWellFormedRecursion 遍历的工作状态： */
	int			selfrefcount;	/* 检测到的自引用数量 */
	RecursionContext context;	/* 允许或不允许自引用的上下文 */
} CteState;


static void fc_analyzeCTE(ParseState *fc_pstate, CommonTableExpr *fc_cte);

/* 依赖处理函数 */
static void fc_makeDependencyGraph(CteState *fc_cstate);
static bool fc_makeDependencyGraphWalker(Node *fc_node, CteState *fc_cstate);
static void fc_TopologicalSort(ParseState *fc_pstate, CteItem *fc_items, int fc_numitems);

/* 递归有效性检查函数 */
static void fc_checkWellFormedRecursion(CteState *fc_cstate);
static bool fc_checkWellFormedRecursionWalker(Node *fc_node, CteState *fc_cstate);
static void fc_checkWellFormedSelectStmt(SelectStmt *fc_stmt, CteState *fc_cstate);


/*
 * transformWithClause -
 *	  将 WITH 子句的“公共表表达式”列表转换为
 *	  查询节点。
 *
 * 结果是转换后的 CTE 列表，将其放入输出
 * 查询中。（这实际上与 p_ctenamespace 的结束值相同，
 * 但在函数的 API 中不暴露显得更干净。）
 */
List * transformWithClause(ParseState *fc_pstate, WithClause *fc_withClause)
{
	ListCell   *fc_lc;

	/* 每个查询级别只能有一个 WITH 子句 */
	Assert(fc_pstate->p_ctenamespace == NIL);
	Assert(fc_pstate->p_future_ctes == NIL);

	/*
	 * 对于任一类型的 WITH，列表中不得有重复的 CTE 名称。
	 * 立即检查这一点，以便我们今后不必担心。
	 *
	 * 此外，暂时将每个 CTE 标记为非递归，并将其
	 * 引用计数初始化为零，并在需要时设置 pstate->p_hasModifyingCTE。
	 */
	foreach(fc_lc, fc_withClause->ctes)
	{
		CommonTableExpr *fc_cte = (CommonTableExpr *) lfirst(fc_lc);
		ListCell   *fc_rest;

		/* MERGE 被解析器允许，但未实现。暂时拒绝 */
		if (IsA(fc_cte->ctequery, MergeStmt))
			ereport(ERROR,
					errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
					errmsg("MERGE not supported in WITH query"),
					parser_errposition(fc_pstate, fc_cte->location));

		for_each_cell(fc_rest, fc_withClause->ctes, lnext(fc_withClause->ctes, fc_lc))
		{
			CommonTableExpr *fc_cte2 = (CommonTableExpr *) lfirst(fc_rest);

			if (strcmp(fc_cte->ctename, fc_cte2->ctename) == 0)
				ereport(ERROR,
						(errcode(ERRCODE_DUPLICATE_ALIAS),
						 errmsg("WITH query name \"%s\" specified more than once",
								fc_cte2->ctename),
						 parser_errposition(fc_pstate, fc_cte2->location)));
		}

		fc_cte->cterecursive = false;
		fc_cte->cterefcount = 0;

		if (!IsA(fc_cte->ctequery, SelectStmt))
		{
			/* 必须是一个数据修改语句 */
			Assert(IsA(fc_cte->ctequery, InsertStmt) ||
				   IsA(fc_cte->ctequery, UpdateStmt) ||
				   IsA(fc_cte->ctequery, DeleteStmt));

			fc_pstate->p_hasModifyingCTE = true;
		}
	}

	if (fc_withClause->recursive)
	{
		/*
		 * 对于 WITH RECURSIVE，如果需要，我们会重新排列列表元素以
		 * 消除前向引用。首先，构建一个工作数组并设置
		 * 树遍历所需的数据结构。
		 */
		CteState	fc_cstate;
		int			fc_i;

		fc_cstate.pstate = fc_pstate;
		fc_cstate.numitems = list_length(fc_withClause->ctes);
		fc_cstate.items = (CteItem *) palloc0(fc_cstate.numitems * sizeof(CteItem));
		fc_i = 0;
		foreach(fc_lc, fc_withClause->ctes)
		{
			fc_cstate.items[fc_i].cte = (CommonTableExpr *) lfirst(fc_lc);
			fc_cstate.items[fc_i].id = fc_i;
			fc_i++;
		}

		/*
		 * 找到所有依赖项并将 CteItems 排序为安全
		 * 处理顺序。同时，标记包含自引用的 CTEs。
		 */
		fc_makeDependencyGraph(&fc_cstate);

		/*
		 * 检查递归查询是否格式正确。
		 */
		fc_checkWellFormedRecursion(&fc_cstate);

		/*
		 * 为解析分析设置 ctenamespace。根据规范，所有 WITH
		 * 项对所有其他项可见，因此在解析分析之前将它们全部放入。
		 * 我们以安全处理顺序构建列表，以便规划程序可以顺序处理查询。
		 */
		for (fc_i = 0; fc_i < fc_cstate.numitems; fc_i++)
		{
			CommonTableExpr *fc_cte = fc_cstate.items[fc_i].cte;

			fc_pstate->p_ctenamespace = lappend(fc_pstate->p_ctenamespace, fc_cte);
		}

		/*
		 * 按照拓扑排序确定的顺序进行解析分析。
		 */
		for (fc_i = 0; fc_i < fc_cstate.numitems; fc_i++)
		{
			CommonTableExpr *fc_cte = fc_cstate.items[fc_i].cte;

			fc_analyzeCTE(fc_pstate, fc_cte);
		}
	}
	else
	{
		/*
		 * 对于非递归 WITH，只需按顺序分析每个 CTE，然后
		 * 将其添加到 ctenamespace。这对应于规范的
		 * 每个 WITH 名称的作用域定义。然而，为了让错误
		 * 报告能够注意到可能存在的错误引用，
		 * 我们在 p_future_ctes 中维护了一个尚不可见 CTEs 的列表。
		 */
		fc_pstate->p_future_ctes = list_copy(fc_withClause->ctes);

		foreach(fc_lc, fc_withClause->ctes)
		{
			CommonTableExpr *fc_cte = (CommonTableExpr *) lfirst(fc_lc);

			fc_analyzeCTE(fc_pstate, fc_cte);
			fc_pstate->p_ctenamespace = lappend(fc_pstate->p_ctenamespace, fc_cte);
			fc_pstate->p_future_ctes = list_delete_first(fc_pstate->p_future_ctes);
		}
	}

	return fc_pstate->p_ctenamespace;
}


/*
 * 对一个 CTE 执行实际的解析分析转换。所有
 * 依赖的 CTEs 已经加载到 pstate->p_ctenamespace 中，
 * 并被标记为正确的输出列名/类型。
 */
static void fc_analyzeCTE(ParseState *fc_pstate, CommonTableExpr *fc_cte)
{
	Query	   *fc_query;
	CTESearchClause *fc_search_clause = fc_cte->search_clause;
	CTECycleClause *fc_cycle_clause = fc_cte->cycle_clause;

	/* 分析尚未完成 */
	Assert(!IsA(fc_cte->ctequery, Query));

	/*
	 * 在分析 CTE 的查询之前，我们最好先识别
	 * 循环标记列的数据类型（如果有），因为查询可能
	 * 会引用它。循环子句的其他有效性检查将在之后进行。
	 */
	if (fc_cycle_clause)
	{
		TypeCacheEntry *fc_typentry;
		Oid			fc_op;

		fc_cycle_clause->cycle_mark_value =
			transformExpr(fc_pstate, fc_cycle_clause->cycle_mark_value,
						  EXPR_KIND_CYCLE_MARK);
		fc_cycle_clause->cycle_mark_default =
			transformExpr(fc_pstate, fc_cycle_clause->cycle_mark_default,
						  EXPR_KIND_CYCLE_MARK);

		fc_cycle_clause->cycle_mark_type =
			select_common_type(fc_pstate,
							   list_make2(fc_cycle_clause->cycle_mark_value,
										  fc_cycle_clause->cycle_mark_default),
							   "CYCLE", NULL);
		fc_cycle_clause->cycle_mark_value =
			coerce_to_common_type(fc_pstate,
								  fc_cycle_clause->cycle_mark_value,
								  fc_cycle_clause->cycle_mark_type,
								  "CYCLE/SET/TO");
		fc_cycle_clause->cycle_mark_default =
			coerce_to_common_type(fc_pstate,
								  fc_cycle_clause->cycle_mark_default,
								  fc_cycle_clause->cycle_mark_type,
								  "CYCLE/SET/DEFAULT");

		fc_cycle_clause->cycle_mark_typmod =
			select_common_typmod(fc_pstate,
								 list_make2(fc_cycle_clause->cycle_mark_value,
											fc_cycle_clause->cycle_mark_default),
								 fc_cycle_clause->cycle_mark_type);

		fc_cycle_clause->cycle_mark_collation =
			select_common_collation(fc_pstate,
									list_make2(fc_cycle_clause->cycle_mark_value,
											   fc_cycle_clause->cycle_mark_default),
									true);

		/* 如果我们顺便查找相关的 <> 操作符也不错 */
		fc_typentry = lookup_type_cache(fc_cycle_clause->cycle_mark_type,
									 TYPECACHE_EQ_OPR);
		if (!OidIsValid(fc_typentry->eq_opr))
			ereport(ERROR,
					errcode(ERRCODE_UNDEFINED_FUNCTION),
					errmsg("could not identify an equality operator for type %s",
						   format_type_be(fc_cycle_clause->cycle_mark_type)));
		fc_op = get_negator(fc_typentry->eq_opr);
		if (!OidIsValid(fc_op))
			ereport(ERROR,
					errcode(ERRCODE_UNDEFINED_FUNCTION),
					errmsg("could not identify an inequality operator for type %s",
						   format_type_be(fc_cycle_clause->cycle_mark_type)));

		fc_cycle_clause->cycle_mark_neop = fc_op;
	}

	/* 现在我们可以开始分析CTE的查询 */
	fc_query = parse_sub_analyze(fc_cte->ctequery, fc_pstate, fc_cte, false, true);
	fc_cte->ctequery = (Node *) fc_query;

	/*
	 * 检查我们是否得到了合理的内容。这前两种情况应
	 * 该被语法禁止。
	 */
	if (!IsA(fc_query, Query))
		elog(ERROR, "unexpected non-Query statement in WITH");
	if (fc_query->utilityStmt != NULL)
		elog(ERROR, "unexpected utility statement in WITH");

	/*
	 * 我们不允许在查询的顶层以外的数据修改WITH，
	 * 因为不清楚这种修改何时应被执行。
	 */
	if (fc_query->commandType != CMD_SELECT &&
		fc_pstate->parentParseState != NULL)
		ereport(ERROR,
				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
				 errmsg("WITH clause containing a data-modifying statement must be at the top level"),
				 parser_errposition(fc_pstate, fc_cte->location)));

	/*
	 * CTE查询始终标记为不可设置标签。(当前这对数据修改语句
	 * 来说才重要，因为该标志将被传播到ModifyTable计划节点。)
	 */
	fc_query->canSetTag = false;

	if (!fc_cte->cterecursive)
	{
		/* 如果尚未完成，则计算输出列名称/类型 */
		analyzeCTETargetList(fc_pstate, fc_cte, GetCTETargetList(fc_cte));
	}
	else
	{
		/*
		 * 验证先前确定的输出列类型和排序规则是否与查询实际
		 * 生成的内容匹配。我们必须检查
		 * 这一点，因为递归项可能已覆盖了
		 * 非递归项，并且我们没有任何简单的方法来修复它。
		 */
		ListCell   *fc_lctlist,
				   *fc_lctyp,
				   *fc_lctypmod,
				   *fc_lccoll;
		int			fc_varattno;

		fc_lctyp = list_head(fc_cte->ctecoltypes);
		fc_lctypmod = list_head(fc_cte->ctecoltypmods);
		fc_lccoll = list_head(fc_cte->ctecolcollations);
		fc_varattno = 0;
		foreach(fc_lctlist, GetCTETargetList(fc_cte))
		{
			TargetEntry *fc_te = (TargetEntry *) lfirst(fc_lctlist);
			Node	   *fc_texpr;

			if (fc_te->resjunk)
				continue;
			fc_varattno++;
			Assert(fc_varattno == fc_te->resno);
			if (fc_lctyp == NULL || fc_lctypmod == NULL || fc_lccoll == NULL)	/* 不应该发生 */
				elog(ERROR, "wrong number of output columns in WITH");
			fc_texpr = (Node *) fc_te->expr;
			if (exprType(fc_texpr) != lfirst_oid(fc_lctyp) ||
				exprTypmod(fc_texpr) != lfirst_int(fc_lctypmod))
				ereport(ERROR,
						(errcode(ERRCODE_DATATYPE_MISMATCH),
						 errmsg("recursive query \"%s\" column %d has type %s in non-recursive term but type %s overall",
								fc_cte->ctename, fc_varattno,
								format_type_with_typemod(lfirst_oid(fc_lctyp),
														 lfirst_int(fc_lctypmod)),
								format_type_with_typemod(exprType(fc_texpr),
														 exprTypmod(fc_texpr))),
						 errhint("Cast the output of the non-recursive term to the correct type."),
						 parser_errposition(fc_pstate, exprLocation(fc_texpr))));
			if (exprCollation(fc_texpr) != lfirst_oid(fc_lccoll))
				ereport(ERROR,
						(errcode(ERRCODE_COLLATION_MISMATCH),
						 errmsg("recursive query \"%s\" column %d has collation \"%s\" in non-recursive term but collation \"%s\" overall",
								fc_cte->ctename, fc_varattno,
								get_collation_name(lfirst_oid(fc_lccoll)),
								get_collation_name(exprCollation(fc_texpr))),
						 errhint("Use the COLLATE clause to set the collation of the non-recursive term."),
						 parser_errposition(fc_pstate, exprLocation(fc_texpr))));
			fc_lctyp = lnext(fc_cte->ctecoltypes, fc_lctyp);
			fc_lctypmod = lnext(fc_cte->ctecoltypmods, fc_lctypmod);
			fc_lccoll = lnext(fc_cte->ctecolcollations, fc_lccoll);
		}
		if (fc_lctyp != NULL || fc_lctypmod != NULL || fc_lccoll != NULL)	/* 不应该发生 */
			elog(ERROR, "wrong number of output columns in WITH");
	}

	/*
	 * 现在对SEARCH和CYCLE子句进行有效性检查（如果存在）。
	 */
	if (fc_search_clause || fc_cycle_clause)
	{
		Query	   *fc_ctequery;
		SetOperationStmt *fc_sos;

		if (!fc_cte->cterecursive)
			ereport(ERROR,
					(errcode(ERRCODE_SYNTAX_ERROR),
					 errmsg("WITH query is not recursive"),
					 parser_errposition(fc_pstate, fc_cte->location)));

		/*
		 * SQL要求WITH列表元素（CTE）必须是“可展开的”，
		 * 以允许搜索或循环子句。这是比单纯递归更严格的要求。
		 * 它基本上意味着查询表达式看起来像
		 *
		 * 非递归查询 UNION [ALL] 递归查询
		 *
		 * 并且递归查询本身不是一个集合操作。
		 *
		 * 截至撰写时，这些标准中的大多数已经由
		 * PostgreSQL允许的所有递归CTE满足。在未来，
		 * 如果进一步的变体递归CTE被接受，
		 * 可能需要在这里进行进一步的检查以确定什么是“可展开的”。
		 */

		fc_ctequery = castNode(Query, fc_cte->ctequery);
		Assert(fc_ctequery->setOperations);
		fc_sos = castNode(SetOperationStmt, fc_ctequery->setOperations);

		/*
		 * 这个左侧检查不需要用于可展开性，但
		 * rewriteSearchAndCycle()当前不支持它，因此
		 * 我们在这里捕捉它。
		 */
		if (!IsA(fc_sos->larg, RangeTblRef))
			ereport(ERROR,
					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
					 errmsg("with a SEARCH or CYCLE clause, the left side of the UNION must be a SELECT")));

		if (!IsA(fc_sos->rarg, RangeTblRef))
			ereport(ERROR,
					(errcode(ERRCODE_SYNTAX_ERROR),
					 errmsg("with a SEARCH or CYCLE clause, the right side of the UNION must be a SELECT")));
	}

	if (fc_search_clause)
	{
		ListCell   *fc_lc;
		List	   *fc_seen = NIL;

		foreach(fc_lc, fc_search_clause->search_col_list)
		{
			String	   *fc_colname = lfirst_node(String, fc_lc);

			if (!list_member(fc_cte->ctecolnames, fc_colname))
				ereport(ERROR,
						(errcode(ERRCODE_SYNTAX_ERROR),
						 errmsg("search column \"%s\" not in WITH query column list",
								strVal(fc_colname)),
						 parser_errposition(fc_pstate, fc_search_clause->location)));

			if (list_member(fc_seen, fc_colname))
				ereport(ERROR,
						(errcode(ERRCODE_DUPLICATE_COLUMN),
						 errmsg("search column \"%s\" specified more than once",
								strVal(fc_colname)),
						 parser_errposition(fc_pstate, fc_search_clause->location)));
			fc_seen = lappend(fc_seen, fc_colname);
		}

		if (list_member(fc_cte->ctecolnames, makeString(fc_search_clause->search_seq_column)))
			ereport(ERROR,
					errcode(ERRCODE_SYNTAX_ERROR),
					errmsg("search sequence column name \"%s\" already used in WITH query column list",
						   fc_search_clause->search_seq_column),
					parser_errposition(fc_pstate, fc_search_clause->location));
	}

	if (fc_cycle_clause)
	{
		ListCell   *fc_lc;
		List	   *fc_seen = NIL;

		foreach(fc_lc, fc_cycle_clause->cycle_col_list)
		{
			String	   *fc_colname = lfirst_node(String, fc_lc);

			if (!list_member(fc_cte->ctecolnames, fc_colname))
				ereport(ERROR,
						(errcode(ERRCODE_SYNTAX_ERROR),
						 errmsg("cycle column \"%s\" not in WITH query column list",
								strVal(fc_colname)),
						 parser_errposition(fc_pstate, fc_cycle_clause->location)));

			if (list_member(fc_seen, fc_colname))
				ereport(ERROR,
						(errcode(ERRCODE_DUPLICATE_COLUMN),
						 errmsg("cycle column \"%s\" specified more than once",
								strVal(fc_colname)),
						 parser_errposition(fc_pstate, fc_cycle_clause->location)));
			fc_seen = lappend(fc_seen, fc_colname);
		}

		if (list_member(fc_cte->ctecolnames, makeString(fc_cycle_clause->cycle_mark_column)))
			ereport(ERROR,
					errcode(ERRCODE_SYNTAX_ERROR),
					errmsg("cycle mark column name \"%s\" already used in WITH query column list",
						   fc_cycle_clause->cycle_mark_column),
					parser_errposition(fc_pstate, fc_cycle_clause->location));

		if (list_member(fc_cte->ctecolnames, makeString(fc_cycle_clause->cycle_path_column)))
			ereport(ERROR,
					errcode(ERRCODE_SYNTAX_ERROR),
					errmsg("cycle path column name \"%s\" already used in WITH query column list",
						   fc_cycle_clause->cycle_path_column),
					parser_errposition(fc_pstate, fc_cycle_clause->location));

		if (strcmp(fc_cycle_clause->cycle_mark_column,
				   fc_cycle_clause->cycle_path_column) == 0)
			ereport(ERROR,
					errcode(ERRCODE_SYNTAX_ERROR),
					errmsg("cycle mark column name and cycle path column name are the same"),
					parser_errposition(fc_pstate, fc_cycle_clause->location));
	}

	if (fc_search_clause && fc_cycle_clause)
	{
		if (strcmp(fc_search_clause->search_seq_column,
				   fc_cycle_clause->cycle_mark_column) == 0)
			ereport(ERROR,
					errcode(ERRCODE_SYNTAX_ERROR),
					errmsg("search sequence column name and cycle mark column name are the same"),
					parser_errposition(fc_pstate, fc_search_clause->location));

		if (strcmp(fc_search_clause->search_seq_column,
				   fc_cycle_clause->cycle_path_column) == 0)
			ereport(ERROR,
					errcode(ERRCODE_SYNTAX_ERROR),
					errmsg("search sequence column name and cycle path column name are the same"),
					parser_errposition(fc_pstate, fc_search_clause->location));
	}
}

/*
 * 计算CTE的派生字段，给定转换后的输出目标列表
 *
 * 对于非递归CTE，这是在转换CTE的查询后调用的。
 * 对于递归CTE，我们在转换非递归项后调用它，
 * 并仅传递非递归项发出的目标列表。
 *
 * 注意：在递归情况下，传递的pstate实际上是用于分析
 * CTE查询的，因此它在非递归情况下低一级。这不重要，
 * 因为我们只是在错误消息上下文中使用它。
 */
void analyzeCTETargetList(ParseState *fc_pstate, CommonTableExpr *fc_cte, List *fc_tlist)
{
	int			fc_numaliases;
	int			fc_varattno;
	ListCell   *fc_tlistitem;

	/* 尚未完成... */
	Assert(fc_cte->ctecolnames == NIL);

	/*
	 * 我们需要确定列名称、类型和排序规则。别名
	 * 列名称将覆盖来自查询本身的任何内容。（注意：
	 * SQL规范规定别名列表必须为空或与输出列集的长度
	 * 完全相同；但我们允许它更短以与别名处理保持一致。）
	 */
	fc_cte->ctecolnames = copyObject(fc_cte->aliascolnames);
	fc_cte->ctecoltypes = fc_cte->ctecoltypmods = fc_cte->ctecolcollations = NIL;
	fc_numaliases = list_length(fc_cte->aliascolnames);
	fc_varattno = 0;
	foreach(fc_tlistitem, fc_tlist)
	{
		TargetEntry *fc_te = (TargetEntry *) lfirst(fc_tlistitem);
		Oid			fc_coltype;
		int32		fc_coltypmod;
		Oid			fc_colcoll;

		if (fc_te->resjunk)
			continue;
		fc_varattno++;
		Assert(fc_varattno == fc_te->resno);
		if (fc_varattno > fc_numaliases)
		{
			char	   *fc_attrname;

			fc_attrname = pstrdup(fc_te->resname);
			fc_cte->ctecolnames = lappend(fc_cte->ctecolnames, makeString(fc_attrname));
		}
		fc_coltype = exprType((Node *) fc_te->expr);
		fc_coltypmod = exprTypmod((Node *) fc_te->expr);
		fc_colcoll = exprCollation((Node *) fc_te->expr);

		/*
		 * 如果CTE是递归的，则强制任何
		 * “未知”列的可见列类型为“text”。我们必须在这里处理
		 * 这个问题，因为在进行任何
		 * 尝试将未知输出列强制为其他类型之前，我们是在非递归项上被调用的。
		 * 我们必须在查看递归项之前解决未知问题。
		 *
		 * 列可能包含'foo' COLLATE "bar"，因此如果已经设置
		 * 排序规则，则不要覆盖它。
		 */
		if (fc_cte->cterecursive && fc_coltype == UNKNOWNOID)
		{
			fc_coltype = TEXTOID;
			fc_coltypmod = -1;		/* 应该已经是-1，但要确认 */
			if (!OidIsValid(fc_colcoll))
				fc_colcoll = DEFAULT_COLLATION_OID;
		}
		fc_cte->ctecoltypes = lappend_oid(fc_cte->ctecoltypes, fc_coltype);
		fc_cte->ctecoltypmods = lappend_int(fc_cte->ctecoltypmods, fc_coltypmod);
		fc_cte->ctecolcollations = lappend_oid(fc_cte->ctecolcollations, fc_colcoll);
	}
	if (fc_varattno < fc_numaliases)
		ereport(ERROR,
				(errcode(ERRCODE_INVALID_COLUMN_REFERENCE),
				 errmsg("WITH query \"%s\" has %d columns available but %d columns specified",
						fc_cte->ctename, fc_varattno, fc_numaliases),
				 parser_errposition(fc_pstate, fc_cte->location)));
}


/*
 * 确定一组WITH RECURSIVE项的交叉引用，
 * 并按没有前向引用的顺序进行排序。
 */
static void fc_makeDependencyGraph(CteState *fc_cstate)
{
	int			fc_i;

	for (fc_i = 0; fc_i < fc_cstate->numitems; fc_i++)
	{
		CommonTableExpr *fc_cte = fc_cstate->items[fc_i].cte;

		fc_cstate->curitem = fc_i;
		fc_cstate->innerwiths = NIL;
		fc_makeDependencyGraphWalker((Node *) fc_cte->ctequery, fc_cstate);
		Assert(fc_cstate->innerwiths == NIL);
	}

	fc_TopologicalSort(fc_cstate->pstate, fc_cstate->items, fc_cstate->numitems);
}

/*
 * 树遍历函数以检测
 * WITH RECURSIVE列表中CTE的交叉引用和自引用。
 */
static bool fc_makeDependencyGraphWalker(Node *fc_node, CteState *fc_cstate)
{
	if (fc_node == NULL)
		return false;
	if (IsA(fc_node, RangeVar))
	{
		RangeVar   *fc_rv = (RangeVar *) fc_node;

		/* 如果是未限定名称，可能是CTE引用 */
		if (!fc_rv->schemaname)
		{
			ListCell   *fc_lc;
			int			fc_i;

			/* ...但首先看看它是否被内部WITH捕获 */
			foreach(fc_lc, fc_cstate->innerwiths)
			{
				List	   *fc_withlist = (List *) lfirst(fc_lc);
				ListCell   *fc_lc2;

				foreach(fc_lc2, fc_withlist)
				{
					CommonTableExpr *fc_cte = (CommonTableExpr *) lfirst(fc_lc2);

					if (strcmp(fc_rv->relname, fc_cte->ctename) == 0)
						return false;	/* 是的，所以退出 */
				}
			}

			/* 不，可能是对此查询级别的引用 */
			for (fc_i = 0; fc_i < fc_cstate->numitems; fc_i++)
			{
				CommonTableExpr *fc_cte = fc_cstate->items[fc_i].cte;

				if (strcmp(fc_rv->relname, fc_cte->ctename) == 0)
				{
					int			fc_myindex = fc_cstate->curitem;

					if (fc_i != fc_myindex)
					{
						/* 添加交叉项依赖 */
						fc_cstate->items[fc_myindex].depends_on =
							bms_add_member(fc_cstate->items[fc_myindex].depends_on,
										   fc_cstate->items[fc_i].id);
					}
					else
					{
						/* 发现这个是自引用 */
						fc_cte->cterecursive = true;
					}
					break;
				}
			}
		}
		return false;
	}
	if (IsA(fc_node, SelectStmt))
	{
		SelectStmt *fc_stmt = (SelectStmt *) fc_node;
		ListCell   *fc_lc;

		if (fc_stmt->withClause)
		{
			if (fc_stmt->withClause->recursive)
			{
				/*
				 * 在递归情况下，WITH中的所有查询名称对
				 * 所有WITH项以及主查询可见。因此
				 * 将它们全部推入，处理，然后全部弹出。
				 */
				fc_cstate->innerwiths = lcons(fc_stmt->withClause->ctes,
										   fc_cstate->innerwiths);
				foreach(fc_lc, fc_stmt->withClause->ctes)
				{
					CommonTableExpr *fc_cte = (CommonTableExpr *) lfirst(fc_lc);

					(void) fc_makeDependencyGraphWalker(fc_cte->ctequery, fc_cstate);
				}
				(void) raw_expression_tree_walker(fc_node,
												  fc_makeDependencyGraphWalker,
												  (void *) fc_cstate);
				fc_cstate->innerwiths = list_delete_first(fc_cstate->innerwiths);
			}
			else
			{
				/*
				 * 在非递归情况下，查询名称对
				 * 后面的WITH项和主查询可见。
				 */
				fc_cstate->innerwiths = lcons(NIL, fc_cstate->innerwiths);
				foreach(fc_lc, fc_stmt->withClause->ctes)
				{
					CommonTableExpr *fc_cte = (CommonTableExpr *) lfirst(fc_lc);
					ListCell   *fc_cell1;

					(void) fc_makeDependencyGraphWalker(fc_cte->ctequery, fc_cstate);
					/* 注意递归可能会改变innerwiths列表 */
					fc_cell1 = list_head(fc_cstate->innerwiths);
					lfirst(fc_cell1) = lappend((List *) lfirst(fc_cell1), fc_cte);
				}
				(void) raw_expression_tree_walker(fc_node,
												  fc_makeDependencyGraphWalker,
												  (void *) fc_cstate);
				fc_cstate->innerwiths = list_delete_first(fc_cstate->innerwiths);
			}
			/* 我们完成了对SelectStmt的检查 */
			return false;
		}
		/* 如果没有WITH子句，只需继续进行正常处理 */
	}
	if (IsA(fc_node, WithClause))
	{
		/*
		 * 防止raw_expression_tree_walker直接递归进入
		 * WITH子句。我们需要这样做仅在上述代码的控制下。
		 */
		return false;
	}
	return raw_expression_tree_walker(fc_node,
									  fc_makeDependencyGraphWalker,
									  (void *) fc_cstate);
}

/*
 * 按依赖关系排序，使用标准的拓扑排序操作
 */
static void fc_TopologicalSort(ParseState *fc_pstate, CteItem *fc_items, int fc_numitems)
{
	int			fc_i,
				fc_j;

	/* 针对序列中的每个位置... */
	for (fc_i = 0; fc_i < fc_numitems; fc_i++)
	{
		/* ... 扫描剩余项以找到没有依赖关系的项 */
		for (fc_j = fc_i; fc_j < fc_numitems; fc_j++)
		{
			if (bms_is_empty(fc_items[fc_j].depends_on))
				break;
		}

		/* 如果没有找到，依赖图中存在循环 */
		if (fc_j >= fc_numitems)
			ereport(ERROR,
					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
					 errmsg("mutual recursion between WITH items is not implemented"),
					 parser_errposition(fc_pstate, fc_items[fc_i].cte->location)));

		/*
		 * 找到了一个。将其移到前面，并从其他每个项的
		 * 依赖中移除。
		 */
		if (fc_i != fc_j)
		{
			CteItem		fc_tmp;

			fc_tmp = fc_items[fc_i];
			fc_items[fc_i] = fc_items[fc_j];
			fc_items[fc_j] = fc_tmp;
		}

		/*
		 * 直到 i 的项已知没有剩余依赖，因此我们
		 * 可以在此循环中跳过它们。
		 */
		for (fc_j = fc_i + 1; fc_j < fc_numitems; fc_j++)
		{
			fc_items[fc_j].depends_on = bms_del_member(fc_items[fc_j].depends_on,
												 fc_items[fc_i].id);
		}
	}
}


/*
 * 检查递归查询是否格式正确。
 */
static void fc_checkWellFormedRecursion(CteState *fc_cstate)
{
	int			fc_i;

	for (fc_i = 0; fc_i < fc_cstate->numitems; fc_i++)
	{
		CommonTableExpr *fc_cte = fc_cstate->items[fc_i].cte;
		SelectStmt *fc_stmt = (SelectStmt *) fc_cte->ctequery;

		Assert(!IsA(fc_stmt, Query));	/* 尚未分析 */

		/* 忽略未被发现为递归的项目 */
		if (!fc_cte->cterecursive)
			continue;

		/* 必须是一个 SELECT 语句 */
		if (!IsA(fc_stmt, SelectStmt))
			ereport(ERROR,
					(errcode(ERRCODE_INVALID_RECURSION),
					 errmsg("recursive query \"%s\" must not contain data-modifying statements",
							fc_cte->ctename),
					 parser_errposition(fc_cstate->pstate, fc_cte->location)));

		/* 必须有顶级的 UNION */
		if (fc_stmt->op != SETOP_UNION)
			ereport(ERROR,
					(errcode(ERRCODE_INVALID_RECURSION),
					 errmsg("recursive query \"%s\" does not have the form non-recursive-term UNION [ALL] recursive-term",
							fc_cte->ctename),
					 parser_errposition(fc_cstate->pstate, fc_cte->location)));

		/*
		 * 事实上，我们应该坚持在顶级不允许有 WITH，因为
		 * 从语法上讲这会包围 UNION。然而，我们在过去并没有
		 * 这样做，可能现在更改已经太晚。坚持要求 WITH 不能包含自引用。
		 * 在检查 UNION 部分之前测试这一点，以避免在这种情况下发出混淆错误。
		 */
		if (fc_stmt->withClause)
		{
			fc_cstate->curitem = fc_i;
			fc_cstate->innerwiths = NIL;
			fc_cstate->selfrefcount = 0;
			fc_cstate->context = RECURSION_SUBLINK;
			fc_checkWellFormedRecursionWalker((Node *) fc_stmt->withClause->ctes,
										   fc_cstate);
			Assert(fc_cstate->innerwiths == NIL);
		}

		/*
		 * 不允许在 UNION 顶部使用 ORDER BY 和类似的修饰。这
		 * 是不合理的，因为在只有部分递归查询结果时，无法弄清楚它们
		 * 的意义。（如果我们允许它们，我们必须检查这些子树内部的
		 * 递归引用。至于 WITH，我们必须在检查 UNION 部分之前
		 * 这样做，以避免在这里有递归引用时发出混淆错误。）
		 */
		if (fc_stmt->sortClause)
			ereport(ERROR,
					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
					 errmsg("ORDER BY in a recursive query is not implemented"),
					 parser_errposition(fc_cstate->pstate,
										exprLocation((Node *) fc_stmt->sortClause))));
		if (fc_stmt->limitOffset)
			ereport(ERROR,
					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
					 errmsg("OFFSET in a recursive query is not implemented"),
					 parser_errposition(fc_cstate->pstate,
										exprLocation(fc_stmt->limitOffset))));
		if (fc_stmt->limitCount)
			ereport(ERROR,
					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
					 errmsg("LIMIT in a recursive query is not implemented"),
					 parser_errposition(fc_cstate->pstate,
										exprLocation(fc_stmt->limitCount))));
		if (fc_stmt->lockingClause)
			ereport(ERROR,
					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
					 errmsg("FOR UPDATE/SHARE in a recursive query is not implemented"),
					 parser_errposition(fc_cstate->pstate,
										exprLocation((Node *) fc_stmt->lockingClause))));

		/*
		 * 现在我们可以继续检查 UNION 操作数本身。
		 *
		 * 左侧操作数完全不能包含自引用。
		 */
		fc_cstate->curitem = fc_i;
		fc_cstate->innerwiths = NIL;
		fc_cstate->selfrefcount = 0;
		fc_cstate->context = RECURSION_NONRECURSIVETERM;
		fc_checkWellFormedRecursionWalker((Node *) fc_stmt->larg, fc_cstate);
		Assert(fc_cstate->innerwiths == NIL);

		/* 右侧操作数应包含一个有效位置的引用 */
		fc_cstate->curitem = fc_i;
		fc_cstate->innerwiths = NIL;
		fc_cstate->selfrefcount = 0;
		fc_cstate->context = RECURSION_OK;
		fc_checkWellFormedRecursionWalker((Node *) fc_stmt->rarg, fc_cstate);
		Assert(fc_cstate->innerwiths == NIL);
		if (fc_cstate->selfrefcount != 1)	/* 不应该发生 */
			elog(ERROR, "missing recursive reference");
	}
}

/*
 * 树 walker 函数，用于检测递归查询中的无效自引用。
 */
static bool fc_checkWellFormedRecursionWalker(Node *fc_node, CteState *fc_cstate)
{
	RecursionContext fc_save_context = fc_cstate->context;

	if (fc_node == NULL)
		return false;
	if (IsA(fc_node, RangeVar))
	{
		RangeVar   *fc_rv = (RangeVar *) fc_node;

		/* 如果是未限定名称，可能是CTE引用 */
		if (!fc_rv->schemaname)
		{
			ListCell   *fc_lc;
			CommonTableExpr *fc_mycte;

			/* ...但首先看看它是否被内部WITH捕获 */
			foreach(fc_lc, fc_cstate->innerwiths)
			{
				List	   *fc_withlist = (List *) lfirst(fc_lc);
				ListCell   *fc_lc2;

				foreach(fc_lc2, fc_withlist)
				{
					CommonTableExpr *fc_cte = (CommonTableExpr *) lfirst(fc_lc2);

					if (strcmp(fc_rv->relname, fc_cte->ctename) == 0)
						return false;	/* 是的，所以退出 */
				}
			}

			/* 不，可能是对此查询级别的引用 */
			fc_mycte = fc_cstate->items[fc_cstate->curitem].cte;
			if (strcmp(fc_rv->relname, fc_mycte->ctename) == 0)
			{
				/* 找到了对活动查询的递归引用 */
				if (fc_cstate->context != RECURSION_OK)
					ereport(ERROR,
							(errcode(ERRCODE_INVALID_RECURSION),
							 errmsg(recursion_errormsgs[fc_cstate->context],
									fc_mycte->ctename),
							 parser_errposition(fc_cstate->pstate,
												fc_rv->location)));
				/* 计数引用 */
				if (++(fc_cstate->selfrefcount) > 1)
					ereport(ERROR,
							(errcode(ERRCODE_INVALID_RECURSION),
							 errmsg("recursive reference to query \"%s\" must not appear more than once",
									fc_mycte->ctename),
							 parser_errposition(fc_cstate->pstate,
												fc_rv->location)));
			}
		}
		return false;
	}
	if (IsA(fc_node, SelectStmt))
	{
		SelectStmt *fc_stmt = (SelectStmt *) fc_node;
		ListCell   *fc_lc;

		if (fc_stmt->withClause)
		{
			if (fc_stmt->withClause->recursive)
			{
				/*
				 * 在递归情况下，WITH中的所有查询名称对
				 * 所有WITH项以及主查询可见。因此
				 * 将它们全部推入，处理，然后全部弹出。
				 */
				fc_cstate->innerwiths = lcons(fc_stmt->withClause->ctes,
										   fc_cstate->innerwiths);
				foreach(fc_lc, fc_stmt->withClause->ctes)
				{
					CommonTableExpr *fc_cte = (CommonTableExpr *) lfirst(fc_lc);

					(void) fc_checkWellFormedRecursionWalker(fc_cte->ctequery, fc_cstate);
				}
				fc_checkWellFormedSelectStmt(fc_stmt, fc_cstate);
				fc_cstate->innerwiths = list_delete_first(fc_cstate->innerwiths);
			}
			else
			{
				/*
				 * 在非递归情况下，查询名称对
				 * 后面的WITH项和主查询可见。
				 */
				fc_cstate->innerwiths = lcons(NIL, fc_cstate->innerwiths);
				foreach(fc_lc, fc_stmt->withClause->ctes)
				{
					CommonTableExpr *fc_cte = (CommonTableExpr *) lfirst(fc_lc);
					ListCell   *fc_cell1;

					(void) fc_checkWellFormedRecursionWalker(fc_cte->ctequery, fc_cstate);
					/* 注意递归可能会改变innerwiths列表 */
					fc_cell1 = list_head(fc_cstate->innerwiths);
					lfirst(fc_cell1) = lappend((List *) lfirst(fc_cell1), fc_cte);
				}
				fc_checkWellFormedSelectStmt(fc_stmt, fc_cstate);
				fc_cstate->innerwiths = list_delete_first(fc_cstate->innerwiths);
			}
		}
		else
			fc_checkWellFormedSelectStmt(fc_stmt, fc_cstate);
		/* 我们完成了对SelectStmt的检查 */
		return false;
	}
	if (IsA(fc_node, WithClause))
	{
		/*
		 * 防止raw_expression_tree_walker直接递归进入
		 * WITH子句。我们需要这样做仅在上述代码的控制下。
		 */
		return false;
	}
	if (IsA(fc_node, JoinExpr))
	{
		JoinExpr   *fc_j = (JoinExpr *) fc_node;

		switch (fc_j->jointype)
		{
			case JOIN_INNER:
				fc_checkWellFormedRecursionWalker(fc_j->larg, fc_cstate);
				fc_checkWellFormedRecursionWalker(fc_j->rarg, fc_cstate);
				fc_checkWellFormedRecursionWalker(fc_j->quals, fc_cstate);
				break;
			case JOIN_LEFT:
				fc_checkWellFormedRecursionWalker(fc_j->larg, fc_cstate);
				if (fc_save_context == RECURSION_OK)
					fc_cstate->context = RECURSION_OUTERJOIN;
				fc_checkWellFormedRecursionWalker(fc_j->rarg, fc_cstate);
				fc_cstate->context = fc_save_context;
				fc_checkWellFormedRecursionWalker(fc_j->quals, fc_cstate);
				break;
			case JOIN_FULL:
				if (fc_save_context == RECURSION_OK)
					fc_cstate->context = RECURSION_OUTERJOIN;
				fc_checkWellFormedRecursionWalker(fc_j->larg, fc_cstate);
				fc_checkWellFormedRecursionWalker(fc_j->rarg, fc_cstate);
				fc_cstate->context = fc_save_context;
				fc_checkWellFormedRecursionWalker(fc_j->quals, fc_cstate);
				break;
			case JOIN_RIGHT:
				if (fc_save_context == RECURSION_OK)
					fc_cstate->context = RECURSION_OUTERJOIN;
				fc_checkWellFormedRecursionWalker(fc_j->larg, fc_cstate);
				fc_cstate->context = fc_save_context;
				fc_checkWellFormedRecursionWalker(fc_j->rarg, fc_cstate);
				fc_checkWellFormedRecursionWalker(fc_j->quals, fc_cstate);
				break;
			default:
				elog(ERROR, "unrecognized join type: %d",
					 (int) fc_j->jointype);
		}
		return false;
	}
	if (IsA(fc_node, SubLink))
	{
		SubLink    *fc_sl = (SubLink *) fc_node;

		/*
		 * 我们故意覆盖外部上下文，因为子查询是
		 * 独立的。
		 */
		fc_cstate->context = RECURSION_SUBLINK;
		fc_checkWellFormedRecursionWalker(fc_sl->subselect, fc_cstate);
		fc_cstate->context = fc_save_context;
		fc_checkWellFormedRecursionWalker(fc_sl->testexpr, fc_cstate);
		return false;
	}
	return raw_expression_tree_walker(fc_node,
									  fc_checkWellFormedRecursionWalker,
									  (void *) fc_cstate);
}

/*
 * checkWellFormedRecursionWalker 的子例程：处理 SelectStmt
 * 而不考虑其 WITH 子句
 */
static void fc_checkWellFormedSelectStmt(SelectStmt *fc_stmt, CteState *fc_cstate)
{
	RecursionContext fc_save_context = fc_cstate->context;

	if (fc_save_context != RECURSION_OK)
	{
		/* 只需递归，而不更改状态 */
		raw_expression_tree_walker((Node *) fc_stmt,
								   fc_checkWellFormedRecursionWalker,
								   (void *) fc_cstate);
	}
	else
	{
		switch (fc_stmt->op)
		{
			case SETOP_NONE:
			case SETOP_UNION:
				raw_expression_tree_walker((Node *) fc_stmt,
										   fc_checkWellFormedRecursionWalker,
										   (void *) fc_cstate);
				break;
			case SETOP_INTERSECT:
				if (fc_stmt->all)
					fc_cstate->context = RECURSION_INTERSECT;
				fc_checkWellFormedRecursionWalker((Node *) fc_stmt->larg,
											   fc_cstate);
				fc_checkWellFormedRecursionWalker((Node *) fc_stmt->rarg,
											   fc_cstate);
				fc_cstate->context = fc_save_context;
				fc_checkWellFormedRecursionWalker((Node *) fc_stmt->sortClause,
											   fc_cstate);
				fc_checkWellFormedRecursionWalker((Node *) fc_stmt->limitOffset,
											   fc_cstate);
				fc_checkWellFormedRecursionWalker((Node *) fc_stmt->limitCount,
											   fc_cstate);
				fc_checkWellFormedRecursionWalker((Node *) fc_stmt->lockingClause,
											   fc_cstate);
				/* stmt->withClause 在这里被故意忽略 */
				break;
			case SETOP_EXCEPT:
				if (fc_stmt->all)
					fc_cstate->context = RECURSION_EXCEPT;
				fc_checkWellFormedRecursionWalker((Node *) fc_stmt->larg,
											   fc_cstate);
				fc_cstate->context = RECURSION_EXCEPT;
				fc_checkWellFormedRecursionWalker((Node *) fc_stmt->rarg,
											   fc_cstate);
				fc_cstate->context = fc_save_context;
				fc_checkWellFormedRecursionWalker((Node *) fc_stmt->sortClause,
											   fc_cstate);
				fc_checkWellFormedRecursionWalker((Node *) fc_stmt->limitOffset,
											   fc_cstate);
				fc_checkWellFormedRecursionWalker((Node *) fc_stmt->limitCount,
											   fc_cstate);
				fc_checkWellFormedRecursionWalker((Node *) fc_stmt->lockingClause,
											   fc_cstate);
				/* stmt->withClause 在这里被故意忽略 */
				break;
			default:
				elog(ERROR, "unrecognized set op: %d",
					 (int) fc_stmt->op);
		}
	}
}
